class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int str_len=s.size();
        int dict_len=wordDict.size();
        int tmp_len=0;
        vector<bool> dp(str_len+1,false);
        dp[0]=true;
        for(int i=0;i<=str_len;i++){
            for(int j=0;j<dict_len;j++){
                tmp_len=wordDict[j].size();
                if(i>=tmp_len&&wordDict[j]==s.substr(i-tmp_len,tmp_len)){
                    dp[i]=dp[i]||dp[i-tmp_len];
                }
            }
        }
        return dp[str_len];
    }
};